import java.util.*;


public class code4 {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param board string字符串一维数组
     * @param word string字符串
     * @return bool布尔型
     */
    public int m;
    public int n;
    public boolean[][] visit;
    public boolean exist (String[] board, String word) {
        m = board.length;
        n = board[0].length();
        visit = new boolean[m][n];

        char[][] boards = new char[m][n];
        for(int i=0;i<m;i++) {
            boards[i] = board[i].toCharArray();
        }

        for(int i=0;i<m;i++) {
            for(int j=0;j<n;j++) {
                if(word.charAt(0) == boards[i][j]) {
                    if(dfs(boards,i,j,word,0)) return true;
                }
            }
        }
        return false;
    }

    public boolean dfs(char[][] boards,int i,int j,String word,int count) {
        if(count == word.length()) return true;
        if(i<0 || i>=m || j<0 || j>=n) return false;

        if(visit[i][j] || word.charAt(count) != boards[i][j]) {
            return false;
        }

        //标记已访问
        visit[i][j] = true;

        boolean ret =  dfs(boards,i+1,j,word,count+1)
                ||dfs(boards,i-1,j,word,count+1)
                ||dfs(boards,i,j+1,word,count+1)
                ||dfs(boards,i,j-1,word,count+1);

        //回溯
        visit[i][j] = false;

        return ret;
    }
}